package com.leetcode.algorithm.y19.m02;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)896. 单调数列
 * (done)888. 公平的糖果交换
 * (done)989. 数组形式的整数加法
 * (done)941. 有效的山脉数组
 * (done)849. 到最近的人的最大距离
 * (done)914. 卡牌分组
 * @author: jie.deng
 * @time: 2019年2月24日 下午10:05:22
 */
public class MySolution0225 {
	/**
	 * 896. 单调数列
	 * 
     * 如果数组是单调递增或单调递减的，那么它是单调的。
     * 
     * 如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
     * 
     * 当给定的数组 A 是单调数组时返回 true，否则返回 false。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：[1,2,2,3]
     * 输出：true
     * 示例 2：
     * 
     * 输入：[6,5,4,4]
     * 输出：true
     * 示例 3：
     * 
     * 输入：[1,3,2]
     * 输出：false
     * 示例 4：
     * 
     * 输入：[1,2,4,5]
     * 输出：true
     * 示例 5：
     * 
     * 输入：[1,1,1]
     * 输出：true
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length <= 50000
     * -100000 <= A[i] <= 100000
	 * @param A
	 * @return
	 */
    public boolean isMonotonic(int[] A) {
		return isAsc(A) || isDesc(A);
    }
    
    private boolean isDesc(int[] nums) {
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] < nums[i + 1]) {
				return false;
			}
		}
		return true;
	}

	private boolean isAsc(int[] nums) {
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] > nums[i + 1]) {
				return false;
			}
		}
		return true;
	}

	/**
     * 888. 公平的糖果交换
     * 
     * 爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 块糖的大小，B[j] 是鲍勃拥有的第 j 块糖的大小。
     * 
     * 因为他们是朋友，所以他们想交换一个糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）
     * 
     * 返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。
     * 
     * 如果有多个答案，你可以返回其中任何一个。保证答案存在。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：A = [1,1], B = [2,2]
     * 输出：[1,2]
     * 示例 2：
     * 
     * 输入：A = [1,2], B = [2,3]
     * 输出：[1,2]
     * 示例 3：
     * 
     * 输入：A = [2], B = [1,3]
     * 输出：[2,3]
     * 示例 4：
     * 
     * 输入：A = [1,2,5], B = [2,4]
     * 输出：[5,4]
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length <= 10000
     * 1 <= B.length <= 10000
     * 1 <= A[i] <= 100000
     * 1 <= B[i] <= 100000
     * 保证爱丽丝与鲍勃的糖果总量不同。
     * 答案肯定存在。
     * @param A
     * @param B
     * @return
     */
	public int[] fairCandySwap(int[] A, int[] B) {
		int[] ret = new int[2];
		Set<Integer> aSet = new HashSet<Integer>(); // 爱丽丝拥有的糖果大小
		Set<Integer> bSet = new HashSet<Integer>(); // 鲍勃拥有的糖果大小
		int sumA = 0;// 爱丽丝的糖果总量
		for (int i = 0; i < A.length; i++) {
			sumA += A[i];
			aSet.add(A[i]);
		}
		int sum = sumA;// 爱丽丝和鲍勃的糖果总量之和
		for (int i = 0; i < B.length; i++) {
			sum += B[i];
			bSet.add(B[i]);
		}
		sum /= 2;
		Set<Integer> set = new HashSet<Integer>(aSet); // 鲍勃拥有的糖果大小
		if (sum == sumA) { // 无需交换糖果的情况
			set.retainAll(bSet); // 求交集
			Integer num = set.iterator().next();
			return new int[] { num, num };
		} else {
			// 为啥加这句话了？ 排序两个set相同的元素，会所有交换的范围，导致错误
			// 比如 输入[31,1,13,66,56,47,3,76,10,70] 和
			// [41,88,10,36,5,94,62,34,17,90]，输出应该是[10,62],把10排除了就找不到了。
			// set.removeAll(bSet);

			for (Integer num : set) {
				if (bSet.contains(num + sum - sumA)) {
					return new int[] { num, num + sum - sumA };
				}
			}
		}
		return ret;
	}
    
    /**
     * 989. 数组形式的整数加法
     * 
     * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
     * 
     * 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：A = [1,2,0,0], K = 34
     * 输出：[1,2,3,4]
     * 解释：1200 + 34 = 1234
     * 解释 2：
     * 
     * 输入：A = [2,7,4], K = 181
     * 输出：[4,5,5]
     * 解释：274 + 181 = 455
     * 示例 3：
     * 
     * 输入：A = [2,1,5], K = 806
     * 输出：[1,0,2,1]
     * 解释：215 + 806 = 1021
     * 示例 4：
     * 
     * 输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
     * 输出：[1,0,0,0,0,0,0,0,0,0,0]
     * 解释：9999999999 + 1 = 10000000000
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length <= 10000
     * 0 <= A[i] <= 9
     * 0 <= K <= 10000
     * 如果 A.length > 1，那么 A[0] != 0
     * @param A
     * @param K
     * @return
     */
	public List<Integer> addToArrayForm(int[] A, int K) {
		List<Integer> list = new ArrayList<Integer>();
		if (K == 0) {
			list.add(0);	// 考虑A=[],K=0的情况
		}else {
			while (K > 0) {
				list.add(0, K % 10);
				K /= 10;
			}
		}

		int size = list.size();
		int len = A.length;
		// 从后往前遍历 list和数组，相加并进位
		int subIdx = 1;//
		while (subIdx <= size && subIdx <= len) {
			list.set(size - subIdx, list.get(size - subIdx) + A[len - subIdx]);
			subIdx++;
		}
		if (len >= subIdx) {
			while (subIdx <= len) {
				list.add(0, A[len - subIdx]);
				subIdx++;
			}
		}
		int sizeNew = list.size();
		for (int i = sizeNew - 1; i >= 0; i--) {
			Integer num = list.get(i);
			if (num >= 10) {
				if (i > 0) {
					list.set(i - 1, list.get(i - 1) + num / 10);// 进位，前一位加1
					list.set(i, num % 10); // 当前位-10
				} else {
					list.add(0, num / 10);// 进位，前一位为1
					list.set(1, num % 10); // 当前位-10
					break;
				}
			}
		}
		return list;
	}
    
    /**
     * 941. 有效的山脉数组
     * 
     * 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
     * 
     * 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
     * 
     * A.length >= 3
     * 在 0 < i < A.length - 1 条件下，存在 i 使得：
     * A[0] < A[1] < ... A[i-1] < A[i]
     * A[i] > A[i+1] > ... > A[B.length - 1]
     *  
     * 
     * 示例 1：
     * 
     * 输入：[2,1]
     * 输出：false
     * 示例 2：
     * 
     * 输入：[3,5,5]
     * 输出：false
     * 示例 3：
     * 
     * 输入：[0,3,2,1]
     * 输出：true
     *  
     * 
     * 提示：
     * 
     * 0 <= A.length <= 10000
     * 0 <= A[i] <= 10000  
     * @param A
     * @return
     */
	public boolean validMountainArray(int[] A) {
		int len = A.length;
		if (len < 3) {
			return false;
		}
		if (A[0] >= A[1]) {
			return false;
		}
		int i = 1;
		while (i < len - 1) {
			if (A[i - 1] < A[i]) {
				i++;
			} else {
				break;
			}
		}
		// A[i-1]为最大值
		while (i < len) {
			if (A[i] >= A[i - 1]) {
				return false;
			}
			i++;
		}
		return true;
	}
    
    /**
     * 849. 到最近的人的最大距离
     * 
     * 在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
     * 
     * 至少有一个空座位，且至少有一人坐在座位上。
     * 
     * 亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
     * 
     * 返回他到离他最近的人的最大距离。
     * 
     * 示例 1：
     * 
     * 输入：[1,0,0,0,1,0,1]
     * 输出：2
     * 解释：
     * 如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
     * 如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
     * 因此，他到离他最近的人的最大距离是 2 。 
     * 示例 2：
     * 
     * 输入：[1,0,0,0]
     * 输出：3
     * 解释： 
     * 如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。
     * 这是可能的最大距离，所以答案是 3 。
     * 提示：
     * 
     * 1 <= seats.length <= 20000
     * seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。
     * @param seats
     * @return
     */
	public int maxDistToClosest(int[] seats) {
		int ret = 0;
		int idx = 0;

		// 上一个连续0的起始序号,初始为0
		int lastIdx = 0;
		// 如果起始不为0，确认一个lastIdx
		if (seats[0] != 0) {
			// 找下一个是0的数的序号，确定为lastIdx
			while (idx < seats.length && seats[idx] != 0) {
				idx++;
			}
			lastIdx = idx;
		}

		while (idx < seats.length) {
			// 找第一个不是0的数的序号
			while (idx < seats.length && seats[idx] == 0) {
				idx++;
			}
			if (idx == seats.length) {
				// 没找到，说明数组以连续的0结尾
				if (idx - lastIdx > ret) {
					ret = idx - lastIdx;
				}
				break;
			}
			// 此时，seats[idx] = 1
			if (lastIdx == 0) {
				// 起始为0的情况
				ret = idx - lastIdx;
			} else {
				if ((idx - lastIdx) > (2 * ret - 1)) {
					ret = (idx - lastIdx + 1) / 2;
				}
			}

			// 找下一个是0的数的序号
			while (idx < seats.length && seats[idx] != 0) {
				idx++;
			}
			if (idx == seats.length) {
				// 没找到，说明数组以连续的1结尾
				break;
			} else {
				lastIdx = idx;
			}
		}
		return ret;
	}
    
    /**
     * 914. 卡牌分组
     * 
     * 给定一副牌，每张牌上都写着一个整数。
     * 
     * 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
     * 
     * 每组都有 X 张牌。
     * 组内所有的牌上都写着相同的整数。
     * 仅当你可选的 X >= 2 时返回 true。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：[1,2,3,4,4,3,2,1]
     * 输出：true
     * 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
     * 示例 2：
     * 
     * 输入：[1,1,1,2,2,2,3,3]
     * 输出：false
     * 解释：没有满足要求的分组。
     * 示例 3：
     * 
     * 输入：[1]
     * 输出：false
     * 解释：没有满足要求的分组。
     * 示例 4：
     * 
     * 输入：[1,1]
     * 输出：true
     * 解释：可行的分组是 [1,1]
     * 示例 5：
     * 
     * 输入：[1,1,2,2,2,2]
     * 输出：true
     * 解释：可行的分组是 [1,1]，[2,2]，[2,2]
     * 
     * 提示：
     * 
     * 1 <= deck.length <= 10000
     * 0 <= deck[i] < 10000
     * @param deck
     * @return
     */
	public boolean hasGroupsSizeX(int[] deck) {
		if (deck.length < 2) {
			return false;
		}
		Map<Integer, Integer> cntMap = new HashMap<Integer, Integer>(); // <K,V>
																		// key为牌面上的数字，value为出现的次数
		for (int i = 0; i < deck.length; i++) {
			cntMap.put(deck[i], cntMap.get(deck[i]) == null ? 1 : 1 + cntMap.get(deck[i]));
		}
		List<Integer> cntList = new ArrayList<Integer>(cntMap.values());
		if (cntList.size() == 1) {
			return true;
		}
		while (cntList.size() > 1) {
			// 找最小数
			int min = cntList.get(0);
			for (Integer cnt : cntList) {
				if (cnt < min) {
					min = cnt;
				}
			}
			if (min == 1) {
				return false;
			}
			// 所有数除以最小数，取余数
			int size = cntList.size();
			for (int i = 0; i < size; i++) {
				int cnt = cntList.get(i);
				int remain = cnt % min;
				if (remain == 1) {
					return false;
				}
				cntList.set(i, remain);
			}
			for (Iterator<Integer> iterator = cntList.iterator(); iterator.hasNext();) {
				if (iterator.next() == 0) {
					iterator.remove(); // 已经整除的移除掉
				}
			}
			cntList.add(min);
		}
		return true;
	}
}
